/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-09-07
 * Time: 20:49
 */
public class Test {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    class Solution {
        //二叉搜索树的特性:以中序遍历遍历该数，得到的是一个单调递增的数列每遍历到一个节点，判断该节点是否大于前一个结点值
        //morris遍历实现中序遍历
        public boolean isValidBST(TreeNode root) {
            if(root == null) return true;
            TreeNode prev = null;//标记前一个结点位置
            TreeNode mostRight = null;//寻找左子树最右节点
            TreeNode cur = root;
            while(cur != null){
                mostRight = cur.left;
                if(mostRight != null){//有左子树
                    //寻找最右节点
                    while(mostRight.right != null && mostRight.right != cur){
                        mostRight = mostRight.right;
                    }
                    //第一次到达该节点
                    if(mostRight.right == null){
                        mostRight.right = cur;//指向自己
                        cur = cur.left;//cur往左走
                        continue;
                    }else{//第二次来到该节点
                        mostRight.right = null;//指向null
                    }
                }
                //判断前后节点关系
                if(prev == null){
                    prev = cur;
                }else{
                    if(prev.val >= cur.val){
                        return false;
                    }else{
                        prev = cur;
                    }
                }
                //无左子树,或左子树走往,往右树走
                cur = cur.right;
            }
            return true;
        }
    }
    public static void main(String[] args) {

    }
}
